package momo.multitree.structure;

import java.io.IOException;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.Vector;

import momo.multitree.visual.GraphVisualOutput;
import momo.multitree.visual.PajekGraphOutput;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

public class Graph implements Cloneable
{
	private Log log = LogFactory.getLog(Graph.class);
	private GraphVisualOutput visualTool;
	
	private LinkedHashSet<Node> nodes;
	private LinkedHashSet<Edge> edges;
	private LinkedHashMap<Node, LinkedHashSet<Edge>> edgesOfNode;
	
	public Graph()
	{
		nodes = new LinkedHashSet<Node>();
		edges = new LinkedHashSet<Edge>();
		edgesOfNode = new LinkedHashMap<Node, LinkedHashSet<Edge>>();
		visualTool = new PajekGraphOutput();
	}
	
	public Graph(Graph g)
	{
		this();
		Set<Edge> setEdge = g.getEdges();
		Iterator<Edge> iterEdge = setEdge.iterator();
		while ( iterEdge.hasNext() )
			this.add(iterEdge.next());
		
		Set<Node> setNode = g.getNodes();
		Iterator<Node> iterNode = setNode.iterator();
		while ( iterNode.hasNext() )
			this.add(iterNode.next());
	}
	
	/**
	 * new graph will have the same objects as nodes and edges, but a separate info about connectivity
	 */
	public Graph clone() {	
		Graph cloned = new Graph();
		for (Node node : nodes)
			cloned.add(node);
		for (Edge edge : edges)
			cloned.add(edge);
		return cloned;
	}
	
	/**
	 * initializes a graph from a text file
	 * format will be
	 * <no of nodes>
	 * <node id, workload, stability>
	 * <..... till all nodes dataset>
	 * <no of edges>
	 * <edge id, head node id, tail node id, cost from Head to Tail, cost from TH, latency from HT, latency from TH>
	 * <..... till all edges dataset>
	 * @param description
	 */
	public Graph(Reader in) throws Exception
	{
		//Read the stream
		this();
		int chr;
		StringBuffer buffer = new StringBuffer();
		while ((chr = in.read()) > -1) {
			buffer.append((char)chr);
		}
		in.close();
		
		//start processing
		HashMap<String, Node> mapNode = new HashMap<String, Node>(); 
		String lineBreak = System.getProperty("line.separator");
		String rawData = buffer.toString();
		
		StringTokenizer lineTokens = new StringTokenizer(rawData, lineBreak);
		
		int noOfNodes = Integer.parseInt(lineTokens.nextToken());
		
		Node[] nodes = new Node[noOfNodes];
		for(int i=0; i<noOfNodes; i++)
		{
			String lineOfNodeData = lineTokens.nextToken().trim();
			StringTokenizer nodeTokens = new StringTokenizer( lineOfNodeData, ", " );
			String id = nodeTokens.nextToken().trim();
			double workload = Double.parseDouble(nodeTokens.nextToken().trim());
			double stability = Double.parseDouble(nodeTokens.nextToken().trim());
			nodes[i] = new Node(id, workload, stability);
			mapNode.put(id, nodes[i]);
		}
		
		int noOfEdges = Integer.parseInt(lineTokens.nextToken().trim());
		
		Edge[] edges = new Edge[noOfEdges];
		for(int i=0; i<noOfEdges; i++)
		{
			String lineOfEdgeData = lineTokens.nextToken().trim();
			StringTokenizer edgeTokens = new StringTokenizer( lineOfEdgeData, ", " );
			String edgeId = edgeTokens.nextToken().trim();
			Node headNode = mapNode.get(edgeTokens.nextToken().trim());
			Node tailNode = mapNode.get(edgeTokens.nextToken().trim());
			double latHT = Double.parseDouble(edgeTokens.nextToken().trim());
			double latTH = Double.parseDouble(edgeTokens.nextToken().trim());
			double costHT = Double.parseDouble(edgeTokens.nextToken().trim());
			double costTH = Double.parseDouble(edgeTokens.nextToken().trim());
			edges[i] = new Edge(edgeId, headNode, tailNode, costHT, costTH, latHT, latTH);
			this.add(edges[i]);
		}
	}
	
	public boolean add(Edge edge)
	{	
		if ( contains(edge) )
			return false;
		else
			edges.add(edge);
		
		Node headNode = edge.getHeadNode();
		Node tailNode = edge.getTailNode();
		
		this.add(headNode);
		this.add(tailNode);
		
		addEdge(headNode, edge, edgesOfNode);
		addEdge(tailNode, edge, edgesOfNode);
		
		return true;
	}
	
	public boolean add(Node node)
	{
		if ( !contains(node) )
		{
			nodes.add(node);
			return true;
		}
		return false;
			
	}
	
	private void addEdge(Node node, Edge edge, HashMap<Node, LinkedHashSet<Edge>> hashEdges)
	{
		LinkedHashSet<Edge> curEdges = hashEdges.get(node);
		if ( curEdges == null ) {
			curEdges = new LinkedHashSet<Edge>();
			hashEdges.put(node, curEdges);
		}
		curEdges.add(edge);
	}
	
	public boolean remove(Edge edge)
	{
		//remove from edges set
		if ( edges.remove(edge) )
		{
			//remove from edgesOfNode set
			LinkedHashSet<Edge> edgeSetOfHead = edgesOfNode.get(edge.getHeadNode());
			edgeSetOfHead.remove(edge);
			LinkedHashSet<Edge> edgeSetOfTail = edgesOfNode.get(edge.getTailNode());
			edgeSetOfTail.remove(edge);
			return true;
		}
		return false;
	}
	
	public boolean remove(Node node)
	{
		//remove from nodes set
		if ( nodes.remove(node) )
		{
			Vector<Edge> delSet = new Vector<Edge>();
			
			Set<Edge> set = getEdgesOfNode(node);
			Iterator<Edge> iter = set.iterator();
			while ( iter.hasNext() )
			{
//				Edge edge = iter.next();
//				remove(edge);
				delSet.add(iter.next());
			}
			
//			this is to prevent java.util.ConcurrentModificationException
			for(Edge e: delSet)
				this.remove(e);
			
			return true;
		}
		return false;
	}
	
	public Set<Edge> getEdgesOfNode(Node node)
	{
		LinkedHashSet<Edge> currEdges = edgesOfNode.get(node);
		if (currEdges == null)
			//return null;
			return Collections.unmodifiableSet(new LinkedHashSet<Edge>());
		else
			return Collections.unmodifiableSet(currEdges);
	}
	
	public Node getNode(String id) {
		for (Node node : nodes)
			if (node.getId().equals(id))
				return node;
		throw new IllegalArgumentException("Node with id: "+id+" not found");
	}
	
	/*
	 * returns an edge between n1 and n2, or null if such an edge doesn't exist
	 * throws IllegalStateException if there's more than one edge between two nodes
	 * 
	 */
	public Edge getEdge(Node n1, Node n2) {
		if (n1 == null)
			throw new IllegalArgumentException("n1 is null");
		if (n2 == null)
			throw new IllegalArgumentException("n2 is null");
		Set<Edge> edges = getEdgesOfNode(n1);
		Edge result = null;
		
		for (Edge edge : edges) {
			if (((edge.getHeadNode() == n1) && (edge.getTailNode() == n2)) ||
					((edge.getHeadNode() == n2) && (edge.getTailNode() == n1))) {
				if (result == null)
					result = edge;
				else {
					throw new IllegalStateException("More than one edge between nodes: "+n1+" and "+n2);
				}
			}
		}
		return result;
	}
	
	public Set<Node> getNodes()
	{
		return Collections.unmodifiableSet(nodes);
	}
	
	public Set<Edge> getEdges()
	{
		return Collections.unmodifiableSet(edges);
	}
	
	public Set<Edge> getLeafEdges() {
		Set<Edge> leafEdges = new LinkedHashSet<Edge>();
		for ( Node node : getNodes() ) {
			Set<Edge> edgeSet = getEdgesOfNode(node);
			if ( edgeSet.size() == 1 )
				leafEdges.addAll(edgeSet);
		}
		return Collections.unmodifiableSet( leafEdges );
	}
	
	public Set<Edge> getNonLeafEdges() {
		Set<Edge> nonLeafEdges = new LinkedHashSet<Edge>(getEdges());
		nonLeafEdges.removeAll( getLeafEdges() );
		
		return Collections.unmodifiableSet( nonLeafEdges );
	}
	
	public Set<Node> getLeafNodes() {
		Set<Node> leafNodes = new LinkedHashSet<Node>();
		for ( Node node : getNodes() ) {
			Set<Edge> edgeSet = getEdgesOfNode(node);
			if ( edgeSet.size() == 1 )
				leafNodes.add( node );
		}
		return Collections.unmodifiableSet( leafNodes );
	}
	
	public boolean isLeafNode(Node n) {
		return getLeafNodes().contains(n);
	}
	
	public boolean contains(Edge edge)
	{
		return edges.contains(edge);
	}
	
	public boolean contains(Node node)
	{
		return nodes.contains(node);
	}
	
	public boolean isConnectedGraph()
	{
		Set<Node> tmpSet = getNodes();
		if ( !tmpSet.isEmpty() )
		{
			Node[] nodes = tmpSet.toArray(new Node[0]);
			Node root = nodes[0];
			
			LinkedHashSet<Node> visited = new LinkedHashSet<Node>();
			Vector<Node> toVisit = new Vector<Node>();
			
			toVisit.add(root);
			
			while ( toVisit.size() > 0 )
			{
				Node currNode = toVisit.remove(0);
				visited.add(currNode);
				
				Set<Edge> set = this.getEdgesOfNode(currNode);
				Iterator<Edge> iter = set.iterator();
				
				while ( iter.hasNext() )
				{
					Edge edge = iter.next();
					Node toNode = edge.nextNode(currNode);
					
					if ( !visited.contains(toNode) )
						toVisit.add(toNode);
				}
			}
			return tmpSet.size() == visited.size();
		}
		throw new RuntimeException("No nodes available for checking if its a connected graph");
	}
	
	public boolean hasCycle()
	{
		HashSet<Node> visited = new HashSet<Node>();
		
		Node[] nodes = this.getNodes().toArray(new Node[0]);
		Node currNode = nodes[0];
		visited.add(currNode);
		
		return hasCycle(visited, null, currNode);
	}
	
	private boolean hasCycle(HashSet<Node> visited, Node parent, Node currNode)
	{
//		System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~");
//		System.out.println("Current Node: " + currNode.getId());
//		System.out.println("Parent: " + parent.getId());
		visited.add(currNode);
		
		Set<Edge> set = getEdgesOfNode(currNode);
		Iterator<Edge> iter = set.iterator();
		while ( iter.hasNext() )
		{
			Edge edge = iter.next();
			Node toNode = edge.nextNode(currNode);
			
//			System.out.println("Node To: " + toNode.getId());
			
			if ( !visited.contains(toNode) )
			{
				if ( hasCycle(visited, currNode, toNode) )
					return true;
			}else if ( toNode != parent )
				return true;
		}
		return false;
	}
	
	public boolean compare(Graph graph)
	{
		//compare nodes
		Set<Node> setN1 = getNodes();
		Set<Node> setN2 = graph.getNodes();
		
		Iterator<Node> iterN1 = setN1.iterator();
		while ( iterN1.hasNext() )
		{
			boolean hasSameAttr = false;
			Node node1 = iterN1.next();
			
//			System.out.println("~~~~~~~~~~~~~~~~~~~~");
//			System.out.println(node1.toString());
			
			Iterator<Node> iterN2 = setN2.iterator();
			while ( iterN2.hasNext() )
			{
				Node node2 = iterN2.next();
//				System.out.println("* "+node2.toString());
				if ( node1.compare(node2) )
				{
					hasSameAttr = true;
					break;
				}
			}
			if ( !hasSameAttr )
				return false;
//			System.out.println("~~~~~~~~~~~~~~~~~~~~");
		}
		
		//compare edges
		Set<Edge> setE1 = getEdges();
		Set<Edge> setE2 = graph.getEdges();
		
		Iterator<Edge> iterE1 = setE1.iterator();
		while ( iterE1.hasNext() )
		{
			boolean hasSameAttr = false;
			Edge edge1 = iterE1.next();
			
//			System.out.println("~~~~~~~~~~~~~~~~~~~~");
//			System.out.println(edge1.toString());
			
			Iterator<Edge> iterE2 = setE2.iterator();
			while ( iterE2.hasNext() )
			{
				Edge edge2 = iterE2.next();
				
//				System.out.println("* "+edge2.toString());
				
				if ( edge1.compare(edge2) )
				{
					hasSameAttr = true;
					break;
				}
			}
			if ( !hasSameAttr )
				return false;
			
//			System.out.println("~~~~~~~~~~~~~~~~~~~~");
		}
		
		return true;
	}
	
	public boolean isSymmetricCost() {
		for (Edge edge : edges) {
			if (edge.getCost(edge.getHeadNode()) != edge.getCost(edge.getTailNode()))
				return false;
		}
		return true;
	}
	
	public int getNoOfEdges()
	{
		return edges.size();
	}
	
	public int getNoOfNodes()
	{
		return nodes.size();
	}
	
	public void setVisualTool(GraphVisualOutput visualTool)
	{
		this.visualTool = visualTool;
	}
	
	public void outputVisual(String filename) throws Exception
	{
		visualTool.setGraph(this);
		visualTool.output(filename);
	}
	
	public void outputDatasetFile(String filename) throws Exception
	{
		StringBuffer buffer = new StringBuffer();
		
		int sizeOfNode = nodes.size();
		buffer.append(sizeOfNode+"\n");
		for(Node n: nodes)
			buffer.append(n.getId()+", "+n.getWorkloadRate()+", "+n.getStability()+"\n");
		
		int sizeOfEdge = edges.size();
		buffer.append(sizeOfEdge+"\n");
		for(Edge e: edges)
		{
			Node h = e.getHeadNode();
			Node t = e.getTailNode();
			buffer.append(e.getId()+ ", "
					+ h.getId() + ", "
					+ t.getId() + ", "
					+ e.getLatency(h)+ ", " 
					+ e.getLatency(t) + ", " 
					+ e.getCost(h) + ", " 
					+ e.getCost(t) + "\n");
		}
		
		PrintWriter out = new PrintWriter(filename);
		out.println(buffer.toString());
		out.flush();
		out.close();
	}
	
	public void outputMatlabAdjMatrix(String filename) throws Exception {
		Set<Node> setNode = getNodes();
		Set<Edge> setEdge = getEdges();
		int size = setNode.size();
		if ( size == 0 )
			return;
		
		int arr[][] = new int[size][size];
		for ( int i=0; i<size; i++ )
			for ( int j=0; j<size; j++ )
				arr[i][j] = 0;
		
		Map<Node, Integer> map = new HashMap<Node, Integer>();
		int index = 0;
		for( Node n : setNode )
			map.put(n, index++);
		
		for( Edge e : setEdge ) {
			int headIndex = map.get( e.getHeadNode() );
			int tailIndex = map.get( e.getTailNode() );
			arr[headIndex][tailIndex] = 1;
			arr[tailIndex][headIndex] = 1;
		}
		
		StringBuffer buf = new StringBuffer();
		for ( int i=0; i<size; i++ ) {
			for ( int j=0; j<size; j++ ) {
				buf.append(arr[i][j]+" ");
			}
			buf.append("\n");
		}
		
		PrintWriter out = new PrintWriter(filename);
		out.println(buf.toString());
		out.flush();
		out.close();
	}
	
	/**
	 * Added on 30 Jan 2009
	 * Any nodes and edges that are not within the connected graph of this node, will be removed.
	 * @param node 
	 */
	public boolean leftConnectedGraph(Node node)
	{
		boolean success = false;
		
		if ( !contains(node) )
			throw new NoSuchElementException("No such node is found");
		
		LinkedHashSet<Node> visited = new LinkedHashSet<Node>();
		Vector<Node> toVisit = new Vector<Node>();
		
		toVisit.add(node);
		
		while ( toVisit.size() > 0 )
		{
			Node currNode = toVisit.remove(0);
			visited.add(currNode);
			
			Set<Edge> set = this.getEdgesOfNode(currNode);
			Iterator<Edge> iter = set.iterator();
			
			while ( iter.hasNext() )
			{
				Edge edge = iter.next();
				Node toNode = edge.nextNode(currNode);
				
				if ( !visited.contains(toNode) )
					toVisit.add(toNode);
			}
		}
		
		Vector<Node> toRemove = new Vector<Node>();
		Iterator<Node> iter = getNodes().iterator();
		
		while ( iter.hasNext() )
		{
			Node currNode = iter.next();
			if ( !visited.contains(currNode) )
				toRemove.add(currNode);
		}
		
		for(Node nodeToRemove: toRemove)
		{
			this.remove(nodeToRemove);
			success = true;
		}
		
		return success;
	}
	
	public String toString()
	{
		StringBuffer buffer = new StringBuffer();
		
		Set<Node> setNode = this.getNodes();
		Iterator<Node> iterNode = setNode.iterator();
		while ( iterNode.hasNext() )
			buffer.append(iterNode.next().toString()+"\n");
		
		Set<Edge> setEdge = this.getEdges();
		Iterator<Edge> iterEdge = setEdge.iterator();
		while ( iterEdge.hasNext() )
			buffer.append(iterEdge.next().toString()+"\n");
		
		return buffer.toString();
	}
	
}//end of class Graph
